{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find First and Last Position of Element in Sorted Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: searchRange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #在排序数组中查找元素的第一个和最后一个位置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个按照非递减顺序排列的整数数组 <code>nums</code>，和一个目标值 <code>target</code>。请你找出给定目标值在数组中的开始位置和结束位置。</p>\n",
    "\n",
    "<p>如果数组中不存在目标值 <code>target</code>，返回&nbsp;<code>[-1, -1]</code>。</p>\n",
    "\n",
    "<p>你必须设计并实现时间复杂度为&nbsp;<code>O(log n)</code>&nbsp;的算法解决此问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [<code>5,7,7,8,8,10]</code>, target = 8\n",
    "<strong>输出：</strong>[3,4]</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [<code>5,7,7,8,8,10]</code>, target = 6\n",
    "<strong>输出：</strong>[-1,-1]</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [], target = 0\n",
    "<strong>输出：</strong>[-1,-1]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= nums[i]&nbsp;&lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>nums</code>&nbsp;是一个非递减数组</li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= target&nbsp;&lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-first-and-last-position-of-element-in-sorted-array](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-first-and-last-position-of-element-in-sorted-array](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,7,7,8,8,10]\\n8', '[5,7,7,8,8,10]\\n6', '[]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        lower_bound = self.findBound(nums, target, True)\n",
    "        if lower_bound == -1:\n",
    "            return [-1, -1]\n",
    "        upper_bound = self.findBound(nums, target, False)\n",
    "\n",
    "        return [lower_bound, upper_bound]\n",
    "\n",
    "    def findBound(self, nums, target, isFirst):\n",
    "        N = len(nums)\n",
    "        begin, end = 0, N-1\n",
    "\n",
    "        while begin <= end:\n",
    "            mid = (begin+end)//2\n",
    "            if nums[mid] == target:\n",
    "                if isFirst:\n",
    "                    if mid == begin or nums[mid-1]<target:\n",
    "                        return mid\n",
    "                    else:\n",
    "                        end = mid -1\n",
    "                else:\n",
    "                    if mid == end or nums[mid+1] > target:\n",
    "                        return mid \n",
    "                    begin = mid+1\n",
    "            elif nums[mid] > target:\n",
    "                end = mid - 1\n",
    "            else:\n",
    "                begin = mid+1\n",
    "        return -1\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: 'List[int]', target: 'int') -> 'List[int]':\n",
    "        low=0\n",
    "        high = len(nums)-1\n",
    "        mid=0\n",
    "        result = [-1,-1]\n",
    "        if len(nums)==0:\n",
    "            return result\n",
    "        if target<nums[0] or target>nums[-1]:\n",
    "            return result\n",
    "        while low<=high:\n",
    "            mid =  int((low+high)/2)\n",
    "            print(mid,nums[mid])\n",
    "            if nums[mid]>target:\n",
    "                high = mid-1\n",
    "            elif nums[mid]<target:\n",
    "                low = mid+1\n",
    "            else:\n",
    "                low = mid\n",
    "                high = mid\n",
    "                while( (low-1)>=0 and nums[low-1]==target):\n",
    "                    low-=1\n",
    "                while( (high+1)<=(len(nums)-1) and nums[high+1]==target):\n",
    "                    high +=1\n",
    "                break\n",
    "\n",
    "        if nums[mid]==target:\n",
    "            result = [low,high]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums, target):\n",
    "        left, right = 0, len(nums)-1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            if nums[mid] == target:\n",
    "                s, e, len_ = mid, mid, len(nums)-1\n",
    "                while s >= 0 and nums[s] == target:\n",
    "                    s -= 1\n",
    "                while e <= len_ and nums[e] == target:\n",
    "                    e += 1\n",
    "                return [s+1, e-1]\n",
    "            if target >= nums[mid]:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "\n",
    "        return [-1, -1]\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        def binary_find(p,q,target):\n",
    "            while p<=q:\n",
    "                mid=(p+q)//2\n",
    "                if nums[mid]>target:\n",
    "                    q=mid-1\n",
    "                elif nums[mid]<target:\n",
    "                    p=mid+1\n",
    "                else:\n",
    "                    return mid\n",
    "            return -1\n",
    "        n=len(nums)\n",
    "        index=binary_find(0,n-1,target)\n",
    "        if index==-1:\n",
    "            return [-1,-1]\n",
    "        print(index)\n",
    "        pre,last=index,index\n",
    "        p,q=0,index\n",
    "        while p<q:\n",
    "            mid=(p+q)//2\n",
    "            if nums[mid]==target:\n",
    "                q=mid\n",
    "            else:\n",
    "                p=mid+1\n",
    "        pre=p\n",
    "        p,q=index,n-1\n",
    "        while p<q:\n",
    "            mid=(p+q)//2+1\n",
    "            if nums[mid]==target:\n",
    "                p=mid\n",
    "            else:\n",
    "                q=mid-1\n",
    "        last=p\n",
    "        return [pre,last]\n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if not n: return [-1, -1]\n",
    "        \n",
    "        def searchFirst(start, end):\n",
    "            if start == end:\n",
    "                return end if nums[end] == target else -1\n",
    "\n",
    "            median = (start + end + 1)//2\n",
    "            if nums[start] < target <= nums[median]:\n",
    "                return searchFirst(start+1, median)\n",
    "            elif nums[start] == target:\n",
    "                return start\n",
    "            else:\n",
    "                return searchFirst(median, end)\n",
    "        \n",
    "        def searchLast(start, end):\n",
    "            if start == end:\n",
    "                return end if nums[end] == target else -1\n",
    "\n",
    "            median = (start + end)//2\n",
    "            if nums[median] <= target < nums[end]:\n",
    "                return searchLast(median, end-1)\n",
    "            elif nums[end] == target:\n",
    "                return end\n",
    "            else:\n",
    "                return searchLast(start, median)\n",
    "\n",
    "        return [searchFirst(0, n-1), searchLast(0, n-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def biOrderedSearch(self,nums,target):\n",
    "        if nums == []: return -1\n",
    "        if nums[0] == target: return 0\n",
    "        left = 0\n",
    "        i = -1\n",
    "        right = len(nums) \n",
    "        while right - left > 1 :\n",
    "            ns = nums[left:right]\n",
    "            i = int((left + right) / 2)\n",
    "            if nums[i] == target : return i\n",
    "            elif nums[i] < target:\n",
    "                left = i\n",
    "            else:\n",
    "                right = i\n",
    "        return -1\n",
    "    def searchRange(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        index = self.biOrderedSearch(nums,target)\n",
    "        if index == -1: return [-1,-1]\n",
    "#         print(index)\n",
    "        ret = [-1,-1]\n",
    "        i = index\n",
    "        while i >= 0 and  nums[i] == target:\n",
    "            i -= 1\n",
    "        ret[0] = i+1\n",
    "        i = index\n",
    "        while i < len(nums) and  nums[i] == target:\n",
    "            i += 1\n",
    "        ret[1] = i-1\n",
    "        return ret\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        dt = {}\n",
    "        for i in range(len(nums)):\n",
    "            a = nums[i]\n",
    "            b = dt.get(a, 0)\n",
    "            if b != 0:\n",
    "                dt[a].append(i)\n",
    "            else:\n",
    "                dt[a] = [i,]\n",
    "            #print(dt)\n",
    "\n",
    "        x = dt.get(target, False)\n",
    "        if not x:\n",
    "            return [-1, -1]\n",
    "        else:\n",
    "            return[min(x), max(x)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: 'List[int]', target: 'int') -> 'List[int]':\n",
    "        lo = 0\n",
    "        hi = len(nums)\n",
    "        target_flag = False\n",
    "        tmp = -1\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if nums[mid] < target:\n",
    "                lo = mid + 1\n",
    "            elif nums[mid] > target:\n",
    "                hi = mid\n",
    "            else:\n",
    "                target_flag = True\n",
    "                tmp = mid\n",
    "                break\n",
    "\n",
    "        # this seems O(N). need O(logN)\n",
    "        start = end = tmp\n",
    "        if target_flag:\n",
    "            while start >= 0 and nums[start] == nums[tmp]:\n",
    "                start -= 1\n",
    "            while end <= len(nums) - 1 and nums[end] == nums[tmp]:\n",
    "                end += 1\n",
    "            return start + 1, end - 1\n",
    "        else:\n",
    "            return -1, -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        a=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==target:\n",
    "                a.append(i)\n",
    "        if target not in nums:\n",
    "            return [-1,-1]\n",
    "        else:\n",
    "            return a[0],a[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        return (self.left_range(nums,target), self.right_range(nums,target))\n",
    "    def left_range(self,nums,target):\n",
    "        left = 0\n",
    "        right = len(nums)\n",
    "        while(left<right):\n",
    "            mid = left +(right-left)//2\n",
    "            if nums[mid]==target:\n",
    "                right = mid\n",
    "            elif nums[mid]>target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        if left==len(nums):\n",
    "            return -1\n",
    "        return left if nums[left]==target else -1\n",
    "    def right_range(self,nums,target):\n",
    "        left = 0\n",
    "        right = len(nums)\n",
    "        while(left<right):\n",
    "            mid = left +(right-left)//2\n",
    "            if nums[mid]==target:\n",
    "                left = mid+1\n",
    "            elif nums[mid]>target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        if left==0:\n",
    "            return -1\n",
    "        return left-1 if nums[left-1]==target else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        if not nums:\n",
    "            return [-1,-1]\n",
    "        size = len(nums)\n",
    "        left, right = 0, size-1\n",
    "        while left<right:\n",
    "            mid = (left+right)>>1\n",
    "            if nums[mid]>=target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid +1\n",
    "        first = left\n",
    "        if nums[first]!=target:\n",
    "            return [-1,-1]\n",
    "\n",
    "        left, right = 0, size - 1\n",
    "        while left<right:\n",
    "            mid = (left+right)>>1\n",
    "            if nums[mid]<=target:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        second = left-1 if left<=size-1 and nums[left]!=target else size-1\n",
    "        return [first, second]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if nums[mid]<target:\n",
    "                left = mid + 1\n",
    "            elif nums[mid]>target:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        if (right<0) or nums[right]!=target:\n",
    "            return [-1,-1]\n",
    "        else:res1 = right\n",
    "\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if nums[mid]<target:\n",
    "                left = mid + 1\n",
    "            elif nums[mid]>target:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        res2 = left\n",
    "\n",
    "        return [res2,res1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        if nums.count(target)==0:\n",
    "            return [-1,-1]\n",
    "    \n",
    "        return [nums.index(target),len(nums)-1-nums[::-1].index(target)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        def recur(lb,rb):\n",
    "            if rb-lb+1 == 0 or target < nums[lb] or target > nums[rb]:\n",
    "                return [-1,-1]\n",
    "\n",
    "            pavoit = (lb+rb+1) // 2\n",
    "            if nums[pavoit] == target:\n",
    "                l,r = pavoit,pavoit\n",
    "                while l > 0 and nums[l-1] == target:\n",
    "                    l -= 1\n",
    "                while r < len(nums)-1 and nums[r+1] == target:\n",
    "                    r += 1\n",
    "                return [l,r]\n",
    "            else:\n",
    "                # 查找左半边\n",
    "                if target < nums[pavoit]:\n",
    "                    while pavoit > lb and nums[pavoit-1] == nums[pavoit]:\n",
    "                        pavoit -= 1\n",
    "                    return recur(lb,pavoit-1)\n",
    "\n",
    "                # 查找右半边\n",
    "                else:\n",
    "                    while pavoit < rb and nums[pavoit+1] == nums[pavoit]:\n",
    "                        pavoit += 1\n",
    "                    return recur(pavoit+1,rb)\n",
    "\n",
    "        return recur(0,len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        if len(nums)==0:\n",
    "            return [-1,-1]\n",
    "        \n",
    "        if target not in nums:\n",
    "            return [-1,-1]\n",
    "        \n",
    "        a1=self.searchLeft(nums, target)\n",
    "        b1=self.searchRight(nums,target)\n",
    "\n",
    "        return [a1,b1]\n",
    "\n",
    "    def searchLeft(self,nums,target):\n",
    "        left=0\n",
    "        right=len(nums)-1\n",
    "        while left<right:\n",
    "            mid=left+(right-left)//2\n",
    "            if nums[mid]==target:\n",
    "                right= mid #固定右边界\n",
    "            elif nums[mid]>target:\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "\n",
    "        \n",
    "        return left\n",
    "        \n",
    "\n",
    "    def searchRight(self,nums, target):\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2 + 1 #偏向右边\n",
    "            if nums[mid] == target:\n",
    "                left=mid #固定左边界，找右边界\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        res=[]\n",
    "        if not nums:\n",
    "            return [-1,-1]\n",
    "        def mid_search(left,right):\n",
    "            #print(left,right)\n",
    "            if left>=right:\n",
    "                if target==nums[left]:\n",
    "                    res.append(left)\n",
    "                return\n",
    "            mid=(right-left)//2+left\n",
    "            if target==nums[mid]:\n",
    "                res.append(mid)\n",
    "                #print(res)\n",
    "                mid_search(left,mid)\n",
    "                mid_search(mid+1,right)\n",
    "            elif nums[mid]>target:\n",
    "                mid_search(left,mid)\n",
    "            else:\n",
    "                mid_search(mid+1,right)\n",
    "        mid_search(0,len(nums)-1)\n",
    "        if not res:\n",
    "            return [-1,-1]\n",
    "        else:\n",
    "            return [min(res),max(res)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        if target not in nums:\n",
    "            return [-1, -1]\n",
    "        n = len(nums)\n",
    "        left = bisect.bisect_left(nums, target)\n",
    "        a = [i*(-1) for i in nums[::-1]]\n",
    "        right = bisect.bisect_left(a, -target)\n",
    "        return [left, n - right -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums, target: int):\n",
    "        if len(nums) == 0:\n",
    "            return [-1,-1]\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        middle = 0\n",
    "        while left <= right:\n",
    "            middle = (left+right)//2\n",
    "            if nums[middle] == target:\n",
    "                break\n",
    "            elif nums[middle] < target:\n",
    "                left = middle + 1\n",
    "            else:\n",
    "                right = middle - 1\n",
    "\n",
    "        if nums[middle] == target:\n",
    "            left = middle\n",
    "            while left >= 0 and nums[left] == target:\n",
    "                left = left - 1\n",
    "            right = middle\n",
    "            \n",
    "            while right <= (len(nums) - 1) and nums[right] == target:\n",
    "                right = right + 1\n",
    "            return  [left+1,right-1]\n",
    "        \n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            flag = False\n",
    "            if nums[mid] == target:\n",
    "                flag = True\n",
    "                if target > nums[left]:\n",
    "                    left += 1\n",
    "                    flag = False\n",
    "                if target < nums[right]:\n",
    "                    right -= 1\n",
    "                    flag = False\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "            if flag:\n",
    "                return [left, right]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        l = 0\n",
    "        r = len(nums)-1\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "          \n",
    "            if nums[mid]<target:\n",
    "                l=mid+1\n",
    "            elif nums[mid]>target:\n",
    "                r = mid -1\n",
    "            else:\n",
    "                m = n = mid\n",
    "                while m>=0 and nums[m]==target:\n",
    "                    m-=1\n",
    "                while n<len(nums) and nums[n]==target:\n",
    "                    n+=1\n",
    "                return [m+1,n-1]\n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        def search(target):\n",
    "            lo, hi = 0, len(nums) - 1\n",
    "            while lo <= hi:\n",
    "                mid = lo + (hi - lo) // 2\n",
    "                if nums[mid] < target:\n",
    "                    lo = mid + 1\n",
    "                else:\n",
    "                    hi = mid - 1\n",
    "            return lo\n",
    "\n",
    "        if not nums: return [-1, -1]\n",
    "        ret = search(target)\n",
    "        if ret >= len(nums) or nums[ret] != target:\n",
    "            return [-1, -1] \n",
    "        return [ret, search(target + 1) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        # 二分法 logn 复杂度\n",
    "        def low_bound(nums, target):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left\n",
    "        \n",
    "        start = low_bound(nums, target)\n",
    "        if start == len(nums) or nums[start] != target:\n",
    "            return [-1, -1]\n",
    "        end = low_bound(nums, target + 1) - 1\n",
    "        return [start, end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        def lower_bound(l, target):\n",
    "            left = 0\n",
    "            right = len(l)\n",
    "            while left < right:\n",
    "                mid = (left + right)//2\n",
    "                if l[mid] >= target:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "\n",
    "        start = lower_bound(nums, target)\n",
    "        if start == len(nums) or nums[start] != target:\n",
    "            return [-1,-1]\n",
    "        end = lower_bound(nums, target+1) - 1\n",
    "        return [start,end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lower_bound(self, nums, target):\n",
    "        left, right = -1, len(nums)\n",
    "\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if target > nums[mid]:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return right\n",
    "    \n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        start = self.lower_bound(nums, target)\n",
    "\n",
    "        if start == len(nums) or nums[start] != target:\n",
    "            return [-1, -1]\n",
    "        \n",
    "        end = self.lower_bound(nums, target + 1) - 1\n",
    "\n",
    "        return [start, end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        i, j = 0, len(nums)-1\n",
    "        result = -1\n",
    "        while i <= j:\n",
    "            mid = int((i+j) / 2)\n",
    "            if nums[mid] > target:\n",
    "                j = mid-1\n",
    "            elif nums[mid] < target:\n",
    "                i = mid+1\n",
    "            else:\n",
    "                result = mid\n",
    "                break\n",
    "        if result < 0:\n",
    "            return [-1,-1]\n",
    "        left, right = result, result\n",
    "        while left >= 0 and nums[left] == nums[result]:\n",
    "            left -= 1\n",
    "        while right < len(nums) and nums[right] == nums[result]:\n",
    "            right += 1\n",
    "        return [left+1, right-1]    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        # 排除 target 不在 nums 中的情况\n",
    "        if target not in nums:\n",
    "            return [-1, -1]\n",
    "        res = set()\n",
    "        i, j = 0, len(nums) - 1\n",
    "        # 当 target 在 nums 中，且 nums 中只有一个元素时\n",
    "        if i == j:\n",
    "            return [0, 0]\n",
    "\n",
    "        while i <= j:\n",
    "            if nums[i] == target:\n",
    "                res.add(i)\n",
    "            if nums[j] == target:\n",
    "                res.add(j)\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        res = list(res)\n",
    "        if len(res) == 1:\n",
    "            res.append(res[0])\n",
    "        res = sorted(res)\n",
    "        res = [res[0], res[-1]]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        s = int(len(nums))\n",
    "        if target not in nums:\n",
    "            return [-1,-1]\n",
    "        temp = []\n",
    "        for i in range(s):\n",
    "            if nums[i] == target:\n",
    "                temp.append(i)\n",
    "        return [temp[0] , temp[-1]]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        def searchLeft(nums, target):\n",
    "            # 左边界需要满足两个条件：\n",
    "            # 1. 他的值为target\n",
    "            # 2. 他的左边元素小于他，或者他的下标为0\n",
    "            left, right = 0, len(nums)-1\n",
    "            while left <= right:\n",
    "                mid = (right-left)//2 + left\n",
    "                if nums[mid] == target:\n",
    "                    if mid == 0 or nums[mid-1] < target:\n",
    "                        return mid\n",
    "                    else:\n",
    "                        right = mid - 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return -1\n",
    "        \n",
    "        def searchRight(nums, target):\n",
    "            # 右边界需要满足两个条件：\n",
    "            # 1. 他的值为target\n",
    "            # 2. 他的右边元素大于他，或者他的下标为len(nums)-1\n",
    "            left, right = 0, len(nums)-1\n",
    "            while left <= right:\n",
    "                mid = (right-left)//2 + left\n",
    "                if nums[mid] == target:\n",
    "                    if mid == len(nums)-1 or nums[mid+1] > target:\n",
    "                        return mid\n",
    "                    else:\n",
    "                        left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return -1\n",
    "\n",
    "        return [searchLeft(nums, target), searchRight(nums, target)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def searchRange(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if target not in nums: return [-1,-1]\n",
    "        i, j = bisect_left(nums, target), bisect_right(nums, target)-1\n",
    "\n",
    "        return [i, j]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
